import java.security.acl.Owner;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-25
 * Time: 22:35
 */
public class Solution {

    /**
     *  判断两个单词是否只有一个单词的区别
     * @param str1
     * @param str2
     * @return
     */
    public static boolean canChoose(String str1, String str2){
        if(str1.length() != str2.length()){
            return false;
        }
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        int count = 0;
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i] != arr2[i]){
                count++;
                if(count == 2){
                    return false;
                }
            }
        }
        return true;
    }
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        Set<String> choose = new HashSet<>();
        choose.add(beginWord); // 记录哪些单词已经被用上了
        int count = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                for (String word: wordList) {
                    // 如果这个单词还没有被用过且两个单词之间就只差了一个字母 就可以添加进去
                    // 这里也可以修改单词的其中某一位字母
                    // 用 26 个字母挨个试, 只要新的单词在字典里且没有被用过, 就可以添加到队列
                    if(!choose.contains(word) && canChoose(str, word)){
                        if(word.equals(endWord)){
                            return count+1;
                        }
                        queue.add(word);
                        choose.add(word);
                    }
                }
            }
            // 修改完一层就 ++
            count++;
        }
        return 0;
    }
}
